package com.jiang.专题.动态规划.Q377;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/07 21:25
 */
class Solution {
    // // 完全背包， 考虑顺序（滚动数组压缩空间）
    // public int combinationSum4(int[] nums, int target) {
    //     int[] dp = new int[target + 1]; // dp[i] 表示当目标整数位i时有几种组合
    //     dp[0] = 1; // 当不选数组任何数时， 目标整数为0，有一种组合
    //     for (int i = 1; i <= target; i++) {
    //         for (int num: nums) { // 以num为结尾，dp[i - num]有几种组合
    //             if (i >= num) {
    //                 dp[i] += dp[i - num];
    //             }
    //         }
    //     }
    //     return dp[target];
    // }

    // 二维数组
    public int combinationSum4(int[] nums, int target) {
        int[][] dp = new int[nums.length][target + 1]; // dp[i][j]理解为{不以任何数做结尾(一个数都不选)， 以nums[0]结尾 …… 以nums[i]结尾 }的容量为j的全排列数。

        // 第一列只能表示不以任何数做结尾(一个数都不选)，一种情况
        for(int i = 0; i < nums.length; i++)
            dp[i][0] = 1;

        // 从第二列开始，不可能不以任何数做结尾(一个数都不选)
        for (int j = 1; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                // 在第i == 0时，只能以 nums[0]结尾， 而i >= 1时，则可以以nums[0] …… nums[i - 1] 结尾，这个if判断的是能否不以nums[i]结尾
                if (i >= 1) {
                    dp[i][j]  += dp[i - 1][j];
                }
                // 如果 j >= nums[i] 就可以以 nums[i] 为结尾， j - nums[i] 表示容量剩余， 而nums.length - 1表示以nums[i]结尾后， 前面的数可以以nums[0] …… nums[最大]（任意一个数）结尾。  就是在j - nums[i]容量下以任何数结尾。
                if (j >= nums[i]) {
                    dp[i][j] += dp[nums.length - 1][j - nums[i]];
                }
            }
        }

        return dp[nums.length - 1][target];
    }
}
